package demo2;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-09-02
 * Time: 21:12
 */

import java.util.Arrays;

/**
 * 希尔排序(缩小增量排序) : 先选定一个整数(gap-步长), 然后把带排序数组根据该 gap 分组, 距离相同的一组,并在接着对每一组进行分组
 * 后续分组在按照不同的 gap 进行分组, 直到 gap = 1 时结束分组, 并记录所有距离为 1 的所有数在该组内排序好
 * <p>
 * TODO : 时间复杂度分析, 由于 gap 无法精准确定, 估时间复杂度无法准确分析
 *        空间复杂度分析, 没有额外开辟新的空间 O(1)
 *        希尔排序是对直接插入排序的一种优化, 通过每一个步长分组都进行直接插入排序, 只会越来越有序
 */
public class ShellSort {

    // 调用该方法进行希尔排序
    public void shellSort(int[] array) {
        int gap = array.length;
        while (gap >= 1) {
            // gap 暂且按照 2 的倍数进行
            gap /= 2;
            // 每个步长进行一次分组
            shell(gap, array);
        }
    }

    // 实际是把 i - gap 前面的所有元素视为比较数组进行插入当前 i 位置 (直接插入排序)
    public void shell(int gap, int[] array) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 1, 2, 5, 7, 4, 8, 6, 3};
        ShellSort sort = new ShellSort();
        sort.shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
